package com.asia.algorithmcode.binaryTree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @DESCRIPTION: case1: 当前节点没有左子树，那么就遍历到右子树
 * case2：当前节点有左子树，那么就走到该子树的最右节点，如果最右节点的右指针为空，则将右指针指向当前节点，否则回到当前节点，然后将最右节点的右指针清空
 * 在这个过程中记录第一个逆序对，和可能存在的第二个逆序对，最右交换
 * O(N)的时间复杂度，O(1)的空间复杂度
 * @USER: wanfu
 * @DATE: 2025/4/25 星期五 16:44
 */
public class RecoverTree {

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);


//        n3.left = n1;
//        n3.right = n4;
//        n4.left = n2;
        n1.left = n3;
        n3.right = n2;

        new RecoverTree().recoverTree(n1);

        System.out.println(" ");
    }

    public void recoverTree(TreeNode root) {
        TreeNode cur = root;
        TreeNode prev = null;
        TreeNode first = null;
        TreeNode second = null;

        while (cur != null) {
            if (cur.left == null) {
                if (prev != null && prev.val > cur.val) {
                    if (first == null) {
                        first = prev;
                    }
                    second = cur;
                }

                prev = cur;
                cur = cur.right;
            } else {
                TreeNode temp = cur.left;
                while (temp.right != null && temp.right != cur) {
                    temp = temp.right;
                }
                if (temp.right == null) {
                    temp.right = cur;
                    cur = cur.left;
                } else {
                    temp.right = null;
                    if (prev != null && prev.val > cur.val) {
                        if (first == null) {
                            first = prev;
                        }
                        second = cur;
                    }
                    prev = cur;
                    cur = cur.right;
                }
            }
        }
        if (first != null && second != null) {
            int tempValue = first.val;
            first.val = second.val;
            second.val = tempValue;
        }
    }


}
